13.3 KB · ⇊ 4 parts · ⤓ Micron 13.3 KB · ⤓ HTML 21.1 KB

top

L'mwawalgoritmo Lempel-Ziv-Markov chain (LZMA) è un mwbaalgoritmo utilizzato per la mwbqcompressione dei dati. In fase di sviluppo dal mwbg1998 è utilizzato nel formato di compressione mwbw7z del programma per archiviazione dati mwca7-Zip. L'algoritmo utilizza un dizionario di compressione del tutto simile al mwcqLZ77 e fra le sue caratteristiche peculiari ha un elevato rapporto di compressione (solitamente maggiore del formato mwcgbzip2) e un dizionario di compressione di dimensione variabile (fino a 4 mwcwGbyte).

• Introduzione

• Implementazione in 7-Zip

• Algoritmo

• Esempi di utilizzo dell'algoritmo

• Note

• Collegamenti esterni

LZMA utilizza una versione migliorata e ottimizzata dell'algoritmo di compressione LZ77, sostenuta da un range encoder (codificatore). Nei flussi di dati le sequenze di dimensione e locazione ripetuti vengono compresse in maniera differente.

L'implementazione dell'algoritmo LZMA per il programma mweg7-Zip è disponibile nel LZMA mwewSDK ed è stata resa disponibile dal suo creatore mwfaIgor Pavlov sotto mwfqdominio pubblico ed originariamente distribuita sotto ambedue i termini delle licenze mwfgLGPL e mwfwCommon Public License con l'eccezione dei binari linkati del pacchetto. La versione 4.61 beta è stata diffusa sotto dominio pubblico il 2 novembre 2008. La mwgalibreria di riferimento open source LZMA è scritta in mwgqC++ e presenta le seguenti principali caratteristiche:

• Velocità di compressione: approssimativamente 1 mwhaMiB al secondo con una CPU a 2 mwhqGHz

• Velocità di decompressione: 10-20 MiB al secondo su una CPU a 2mwhw GHz

• Supporto del mwiqmultithreading.

L'attuale LZMA SDK in aggiunta all'originale implementazione C++ ne contiene anche una in mwiwANSI C, mwjaC# e mwjqJava. Esistono anche implementazioni in linguaggio mwjgPascal e mwjwPython. L'implementazione utilizzata per 7-Zip usa molte varianti dei metodi delle catene di hash, mwkqalberi binari e alberi di Patricia come base per l'algoritmo di compressione a dizionario.

Il codice di sola decompressione di LZMA in genere richiede circa 5 mwlakiB di memoria mwlqRAM ed è principalmente determinata dalla dimensione della finestra scorrevole utilizzata durante la decompressione del flusso di dati. L'algoritmo di decompressione LZMA è particolarmente utilizzato nei mwlgsistemi embedded grazie alla sua piccola dimensione in termini di codice, il modesto utilizzo della memoria, la ridotta lunghezza del dizionario, nonché per la licenza di software libero.

Nella compressione LZMA il flusso compresso è rappresentato da un flusso di bit elaborato con un codificatore adattivo binario di range (adaptive binary range coder). Il flusso è suddiviso in due pacchetti, di cui ognuno può descrivere sia un singolo byte o una sequenza LZ77 di lunghezza e distanza implicita o codificata esplicitamente. Esistono 7 tipi di pacchetti:

| Codice pacchetto (sequenza di bit) | Descrizione pacchetto |

|---|---|

| 0 + byteCode | Un singolo byte è codificato con il adaptive binary range coder. Quest'ultimo opera in un contesto basato su alcuni numeri della parte più significativa del precedente byte. In modo dipendente dallo stato della macchina può inoltre codificarlo come un singolo byte codificato come differenza fra il byte in oggetto e l'ultimo byte utilizzato nell'ultima distanza LZ77. |

| 1+0 + len + dist | Tipica sequenza LZ77 in cui viene indicata lunghezza e distanza. |

| 1+1+0+0 | Sequenza LZ77 di un byte. La distanza è l'ultima distanza LZ77 utilizzata. |

| 1+1+0+1 + len | Una sequenza LZ77. La distanza è l'ultima distanza LZ77 utilizzata. |

| 1+1+1+0 + len | Una sequenza LZ77. La distanza è la penultima distanza LZ77 utilizzata. |

| 1+1+1+1+0 + len | Una sequenza LZ77. La distanza è la terzultima distanza LZ77 utilizzata. |

| 1+1+1+1+1 + len | Una sequenza LZ77. La distanza è la quartultima distanza LZ77 utilizzata. |

La lunghezza è codificata nel seguente modo:

| Lunghezza codice (sequenza di bit) | Descrizione |

|---|---|

| 0+ 3 bits | La lunghezza è codificata con 3 bit, ottenendo una lunghezza che varia nel range da 2 a 9. |

| 1+0+ 3 bits | La lunghezza è codificata con 3 bit, ottenendo una lunghezza che varia nel range da 10 a 17. |

| 1+1+ 8 bits | La lunghezza è codificata con 8 bit, ottenendo una lunghezza che varia nel range da 18 a 273 |

La distanza è codificata come segue: per prima cosa una classe di distanza è codificata utilizzando 6 bit. Gli altri 5 bit del codice della distanza codificano l'informazione relativa a quanti bit di distanza diretta devono essere estratti dal flusso dati.

Elenco (in ordine alfabetico) di alcuni programmi che utilizzano o supportano LZMA.

• mwyaCRAMFS con le relative patch applicate.

• mwygCygwin - Incluso nella distribuzione per mwywWindows di mwzaCygwin ed è utilizzata da mwzqMiKTeX.cite-ref-1[1]

• mwawDas U-Boot come metodo di compressione opzionale per i file di immagine del kernel dalla versione v2008.10.

• mwbqDpkg dalla versione 1.13.35.

• mwbwGNU mwcaGRUB (version 2), per la compressione del core.img (solo per mwcqBIOS di piattaforme x86).

• mwcwGNU mwdatar, dalla versione 1.20 con estensione dei file di archivio .tar.lzma o .tlz).

• Inno Setup

• mweaLinux (per la compressione dell'immagine del kernel dalla versione 2.6.30)

• Lzip, programma stabile di compressione a linea di comando analogo agli strumenti di archiviazione gzip e bzip2

• mwfaMan - Compressione delle pagine di mwfqman

• mwfwNullsoft Scriptable Install System (NSIS) un sistema di installazione (installer) guidato da script

• p7zip, versione da riga di comando di 7-zip

• mwgwPeazip, interfaccia grafica per 7z a riga di comando e binari per POSIX

• PiSi (Packages Installed Successfully, as Intended)

• PowerArchiver

• mwiaRPM Package Manager in via sperimentale ha un supporto LZMA dalla versione 4.6.0cite-ref-2[2] e un supporto stabile per LZMA/XZ dalla versione RPM 4.7cite-ref-3[3]

• mwkgSlackware - La distribuzione mwkwSlackware è passata dal formato di pacchetti mwlatgz (basato su mwlqgzip) al mwlgtxz (basato su mwlwxz) dalla versione 13.0

• mwmqSQL Backup della Red-Gate. Fornisce un semplice sistema di compressione e invio dei dati per backup di server SQL.

• mwmwSquashFS con le relative patch applicate.

• Unity motore per videogiochi, utilizza LZMA per comprimere i file web del giocatore.

• UPX, dalla versione (beta) 2.92 in poi comprende come opzionali la compressione LZMA

• mwoaWinZip

• XZ Utils, programma di compressione a linea di comando analogo agli strumenti di archiviazione gzip e bzip2

cite-note-11. ↑ mwqqChristian Schenk, mwqgmwqwCreating a custom package repository, su mwradocs.miktex.org, miktex.org. mwrqURL consultato il 15 ottobre 2008.

cite-note-22. ↑ mwsqmwsgmwswRPM 4.6.0 (4.6.0-rc3), su mwtarpm.org. mwtqURL consultato il 31 dicembre 2008.

cite-note-33. ↑ mwuqmwugmwuwRPM 4.7, su mwvarpm.org. mwvqURL consultato il 15 luglio 2009.

• mwwqOfficial home page, su 7-zip.org.

• mwwwLZMA SDK (Software Development Kit), su 7-zip.org.

• mwxqLZMA Utils = XZ Utils, su tukaani.org.

• mwxwData compression, Compressors & Archivers, su unet.univie.ac.at (archiviato dall'url originale il 1º maggio 2009).